package com.itzmn.newcode.offer;

import java.util.ArrayList;
import java.util.LinkedList;

/**
 * @Author: 张梦楠
 * @Date: 2018/11/17 17:30
 * 简书：https://www.jianshu.com/u/d611be10d1a6
 * 码云：https://gitee.com/zhangqiye
 * @Description: 剑指Offer 序列化二叉树，并且反序列化树
 *    序列化： 将树的节点按照某种方法遍历，如果节点为null，则#! 如果不为空就val!
 *    反序列化： 将字符串转成树
 *  思路：
 *   按照层序遍历树
 *
 *   m没做出、、
 *
 *              5
 *            4   null
 *         3    null
 *       2
 *             8
 *           6  10
 *         5  7 9  11
 */
public class SerializeBinTree {


    public static void main(String[] args) {

        new SerializeBinTree().init();
    }

    public void init(){

        int[] ints = {5,4,0,3,0,2};
        TreeNode root = new TreeNode(ints[0]);
        createTree(ints,root,0);
        String serialize = Serialize(root);
        System.out.println(serialize);
        TreeNode deserialize = Deserialize(serialize);
        System.out.println("111");
    }

    String Serialize(TreeNode root) {

        //层序遍历树

        LinkedList<TreeNode> treeNodes = new LinkedList<>();

        treeNodes.add(root);

        StringBuilder stringBuilder = new StringBuilder();
        while (!treeNodes.isEmpty()){

            TreeNode poll = treeNodes.poll();
            if (poll == null){
                stringBuilder.append("#!");
            }else {
                stringBuilder.append(poll.val+"!");
                treeNodes.add(poll.left);
                treeNodes.add(poll.right);
            }
        }

        return stringBuilder.toString();

    }
    TreeNode Deserialize(String str) {

        String[] split = str.split("!");

        String s = split[0];
        if (s == "#"){
            return null;
        }

        TreeNode root = new TreeNode(Integer.parseInt(split[0]));
        de(split,root,0);
        return root;
    }

    public void de(String[] arrs,TreeNode root,int index){

        boolean left = false;
        boolean right = false;

        if (index*2+1>=arrs.length){
            return;
        }

        int leftval = arrs[index*2+1].equals("#")? 0:Integer.parseInt(arrs[index*2+1]);

        if (leftval==-1){
            return;
        }

        //根节点的左子树是null并且左边没有被插入过
        if (root.left == null && !left){

            if (leftval != 0){
                TreeNode treeNode = new TreeNode(leftval);
                root.left = treeNode;
            }
            left = true;
        }
        if (index*2+2>=arrs.length){
            return;
        }
        int rightval = arrs[index*2+2].equals("#")? 0:Integer.parseInt(arrs[index*2+2]);
        if (rightval == -1){
            return;
        }
        if (root.right == null && !right){
            if (rightval != 0){
                TreeNode treeNode = new TreeNode(rightval);
                root.right = treeNode;
            }
            right = true;
        }

        if (root.left != null){
            de(arrs,root.left,index*2+1);
        }
        if (root.right != null){
            de(arrs,root.right,index*2+2);
        }


    }

    /**
     * 创建二叉树,含有空节点的二叉树
     *  当数组中数据为0时，该节点为null，-1则结束创建或者直至数据插完
     * @param arrs
     * @return
     */
    public void createTree(int[] arrs,TreeNode root,int index){

        boolean left = false;
        boolean right = false;

        if (index*2+1>=arrs.length){
            return;
        }

        int leftval = arrs[index*2+1];

        if (leftval==-1){
            return;
        }

        //根节点的左子树是null并且左边没有被插入过
        if (root.left == null && !left){

            if (leftval != 0){
                TreeNode treeNode = new TreeNode(leftval);
                root.left = treeNode;
            }
            left = true;
        }
        if (index*2+2>=arrs.length){
            return;
        }
        int rightval = arrs[index*2+2];
        if (rightval == -1){
            return;
        }
        if (root.right == null && !right){
            if (rightval != 0){
                TreeNode treeNode = new TreeNode(rightval);
                root.right = treeNode;
            }
            right = true;
        }

        if (root.left != null){
            createTree(arrs,root.left,index*2+1);
        }
        if (root.right != null){
            createTree(arrs,root.right,index*2+2);
        }


    }
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;

        }

    }

}
